package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 平衡二叉树
 * @param <K>
 * @param <V>
 */
public class AVLTree<K extends Comparable<K>,V> {

    private Node root;

    private int size;

    private class Node{
        public K key;
        public V value;
        public Node left,right;
        public int height;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            this.height = 1;
        }

        public int getSize(){
            return size;
        }

        public boolean isEmpty(){
            return size == 0;
        }

        /**
         * 若它的左子树不为空，左子树上所有节点的值都小于它的根节点。
         * 若它的右子树不为空，右子树上所有的节点的值都大于它的根节点。
         * 它的左、右子树也都是二分搜索树。 二分搜索树有着高效的插入、删除、查询操作。
         * 平均时间的时间复杂度为 O (log n) ，最差情况为 O (n) 。
         * 二分搜索树与堆不同，不一定是完全二叉树，底层不容易直接用数组表示故采用链表来实现二分搜索树。
         * 是否为二分搜索树
         * @return true/false
         */

        public boolean isBST(){
            List<K> keys = new ArrayList<>();
            inOrder(root,keys);
            for (int i = 1; i < keys.size(); i++) {
                if(keys.get(i-1).compareTo(keys.get(i)) > 0){
                    return false;
                }
            }
            return true;
        }

        private void inOrder(Node node, List<K> keys) {
            if(node == null){
                return;
            }
            inOrder(node.left,keys);
            keys.add(node.key);
            inOrder(node.left,keys);
        }
        
        public boolean isBalanced(){
            return isBalanced(root);
        }

        private boolean isBalanced(Node node) {
            if(node == null){
                return true;
            }
            int balanceFactor = getBalanceFactor(node);
            if(Math.abs(balanceFactor) > 1){
                return false;
            }
            return isBalanced(node.left) && isBalanced(node.right);
        }

        private int getHeight(Node node){
            return node == null ? 0 : node.height;
        }

        public void add(K key , V value){
            root = add(root,key,value);
        }

        private Node add(Node node, K key, V value) {
            if(node == null){
                size ++;
                return new Node(key,value);
            }

            if(key.compareTo(node.key) < 0){
                node.left = add(node.left,key,value);
            }else if(key.compareTo(node.key) > 0){
                node.right = add(node.right,key,value);
            }else{
                node.value = value;
            }
            node.height = 1 + Math.max(getHeight(node.left),getHeight(node.right));

            int balanceFactor = getBalanceFactor(node);

            // 当前节点不平衡，而且左节点向左倾斜 LL
            if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){
                return  rightRotate(node);
            }

            // 当前节点不平衡，而且右节点向右倾斜 RR
            if(balanceFactor < -1 && getBalanceFactor(node.right) <= 0){
                return  leftRotate(node);
            }

            // 当前节点不平衡，而且右节点向右倾斜 LR
            if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){
                node.left = leftRotate(node.left);
                return  rightRotate(node);
            }

            // 当前节点不平衡，而且右节点向右倾斜 RL
            if(balanceFactor < -1 && getBalanceFactor(node.right) > 0){
                node.right = rightRotate(node.right);
                return  leftRotate(node);
            }

            return node;
        }


        public void remove(K key ){
            root = remove(root,key);
        }

        private Node remove(Node node, K key) {
            if(node == null){
                return  null;
            }

            Node retNode ;

            if(key.compareTo(node.key) < 0){
                node.left = remove(node.left,key);
                retNode =  node;
            }else if(key.compareTo(node.key) > 0){
                node.right = remove(node.right,key);
                retNode =  node;
            }else {
                if(node.left == null){
                    Node rightNode = node.right;
                    node.right = null;
                    size --;
                    retNode =  rightNode;
                }else  if(node.right == null){
                    Node leftNode = node.left;
                    node.left = null;
                    size --;
                    retNode =  leftNode;
                }else {
                    // 节点左子树和右子树都存在，从右子树中找到最小值，和当前的删除节点进行替换
                    Node successor = minnum(node.right);
                    successor.right = remove(node.right,successor.key);
                    successor.left = node.left;
                    node.left = node.right = null;
                    retNode = successor;
                }
            }

            //一种是没有找到，还有一种是找到的是叶子节点，叶子节点删除了
            if(retNode == null){
                return  null;
            }

            retNode.height = 1 + Math.max(getHeight(retNode.left),getHeight(retNode.right));

            int balanceFactor = getBalanceFactor(retNode);

            // 当前节点不平衡，而且左节点向左倾斜 LL
            if(balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0){
                return  rightRotate(retNode);
            }

            // 当前节点不平衡，而且右节点向右倾斜 RR
            if(balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0){
                return  leftRotate(retNode);
            }

            // 当前节点不平衡，而且右节点向右倾斜 LR
            if(balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
                retNode.left = leftRotate(retNode.left);
                return  rightRotate(retNode);
            }

            // 当前节点不平衡，而且右节点向右倾斜 RL
            if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
                retNode.right = rightRotate(retNode.right);
                return  leftRotate(retNode);
            }

            return retNode;

        }

        private Node minnum(Node node) {
            return node.left == null ? node : minnum(node.left);
        }

        /**
         *              y  2
         *             / \
         *            x  T4
         *           / \
         *          z  T3
         *         / \
         *        T1  T2
         *
         *               x
         *            /    \
         *           z      y
         *          / \    / \
         *         T1 T2  T3  T4
         * @param y
         * @return
         */
        private Node rightRotate(Node y){
              Node x  = y.left;
              Node t3 = x.right;
              x.left = y;
              y.left = t3;

              // 更新height
              y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
              x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
              return x;
        }


        /**
         *              y
         *             / \
         *            T4  x
         *               / \
         *            T3    z
         *                 / \
         *                T1  T2
         *
         *               x
         *             /   \
         *           y      z
         *          / \    / \
         *         T4 T3  T1  T2
         * @param y
         * @return
         */
        private Node leftRotate(Node y){
            Node x  = y.right;
            Node t3 = x.left;
            x.right = y;
            y.right = t3;

            // 更新height
            y.height = Math.max(getHeight(y.left),getHeight(y.right))+1;
            x.height = Math.max(getHeight(x.left),getHeight(x.right))+1;
            return x;
        }

        private int getBalanceFactor(Node node){
            return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
        }
    }

}
